package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Random;

/**
 * @author shiminghui
 * @date 2025/3/19 18:45
 * @description: TODO
 */
public class _066_分而治之_快速选择算法 {

    private static Random random = new Random();

    @Test
    public void test1() {
        int[] arr = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(quickSelect(arr, 3, 0, arr.length - 1));
    }

    /**
     * 给你一个数组,然你找出第i大的元素
     */
    private int quickSelect(int[] arr, int i, int left, int right) {
        int partition = partition(arr, left, right);
        if (partition == arr.length - i) {
            return arr[partition];
        } else if (partition > arr.length - i) {
            return quickSelect(arr, i, left, partition - 1);
        } else {
            return quickSelect(arr, i, partition + 1, right);
        }
    }

    @Test
    public void test2() {
        int[] arr = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        // 1 2 2 3 3 4 5 5 6
        System.out.println(findMedian(arr, 0, arr.length - 1, (arr.length - 1) / 2.0));
    }


    /**
     * 给你一个数组,让你找出数组中的中位数
     */
    private double findMedian(int[] arr, int left, int right, double median) {
        int partition = partition(arr, left, right);
        if (partition == median) {
            return arr[partition];
        } else if (partition > median && partition - 1 < median) {
            // 从left 到 partition-1 中找到最大值
            int max = Integer.MIN_VALUE;
            for (int i = left; i < partition; i++) {
                max = Math.max(max, arr[i]);
            }
            return (max + arr[partition]) / 2.0;
        } else if (partition < median && partition + 1 > median) {
            // 从right 到 partition+1 中找到最小值
            int min = Integer.MAX_VALUE;
            for (int i = partition + 1; i <= right; i++) {
                min = Math.min(min, arr[i]);
            }
            return (min + arr[partition]) / 2.0;
        } else if (partition < median) {
            return findMedian(arr, partition + 1, right, median);
        } else {
            return findMedian(arr, left, partition - 1, median);
        }
    }


    /**
     * 分区
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] arr, int left, int right) {
        if (left >= right) {
            return left;
        }
        // 找出一个基准点(随机)
        int index = random.nextInt(right - left + 1) + left;
        // 将基准点放到最右边
        swap(arr, index, right);
        // 遍历,找到比基准点小的,放在左边,比基准点大的,放在右边
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && arr[left] < arr[j]) {
                j--;
            }
            while (i <= j && arr[left] > arr[i]) {
                i++;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (j != left) {
            swap(arr, j, left);
        }
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
